package com.example.leetcode.prcatice;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums​​​ 和一个整数 k​​​​​ 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。
 *
 * 返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,0,3,0], k = 1
 * 输出：3
 * 解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
 *
 */
public class Test1787 {

    /**
     *
     * 这样的性质是可由「答案数组中所有长度为 kk 的区间异或结果为 00」推导出来的：
     *
     * 假设区间 [i, j][i,j] 长度为 kk，其异或结果为 00。即 nums[i] ⊕ nums[i + 1] ⊕ ... ⊕ nums[j] = 0nums[i]⊕nums[i+1]⊕...⊕nums[j]=0
     *
     * 长度不变，将区间整体往后移动一位 [i + 1, j + 1][i+1,j+1]，其异或结果为 00。即 nums[i + 1] ⊕ ... ⊕ nums[j] ⊕ nums[j + 1] = 0nums[i+1]⊕...⊕nums[j]⊕nums[j+1]=0
     *
     * 两式结合，中间 [i + 1, j][i+1,j] 区间的数值出现两次，抵消掉最终剩下 nums[i] ⊕ nums[j + 1] = 0nums[i]⊕nums[j+1]=0，即推出 nums[i]nums[i] 必然等于 num[j + 1]num[j+1]
     *
     *
     * 即每列值相同，首航异或为0即可，看题解
     *
     */

    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int max = 1024;
        int[][] f = new int[k][max];
        int[] g = new int[k];
        for (int i = 0; i < k; i++) {
            Arrays.fill(f[i], 0x3f3f3f3f);
            g[i] = 0x3f3f3f3f;
        }
        for (int i = 0, cnt = 0; i < k; i++, cnt = 0) {
            // 使用 map 和 cnt 分别统计当前列的「每个数的出现次数」和「有多少个数」
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = i; j < n; j += k) {
                map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
                cnt++;
            }
            if (i == 0) { // 第 0 列：只需要考虑如何将该列变为 xor 即可
                for (int xor = 0; xor < max; xor++) {
                    f[0][xor] = Math.min(f[0][xor], cnt - map.getOrDefault(xor, 0));
                    g[0] = Math.min(g[0], f[0][xor]);
                }
            } else { // 其他列：考虑与前面列的关系
                for (int xor = 0; xor < max; xor++) {
                    f[i][xor] = g[i - 1] + cnt; // 整列替换
                    for (int cur : map.keySet()) { // 部分替换
                        f[i][xor] = Math.min(f[i][xor], f[i - 1][xor ^ cur] + cnt - map.get(cur));
                    }
                    g[i] = Math.min(g[i], f[i][xor]);
                }
            }
        }
        return f[k - 1][0];

    }
}
